class Solution {
public:
/*
//数字计数
    int missingNumber(vector<int>& nums) {
        int arr[10000] = {0};
        if(nums.size() == 1){   //只有一个数字
            if(nums[0]){  //nums中没有0
                return 0;
            }
            return 1;  //nums中只有0 ，没有1
        }
        for(int i = 0; i < nums.size();i++){
            ++arr[nums[i]];
        }
        for(int i = 0; i < nums.size();i++){
            if(arr[i] == 0){
                return i;
            }
        }
        return nums.size();   //循环后没有返回：0~n-2每一位都有，返回n-1
    }
*/

//二分查找第一个值与下标不相等的元素
    int missingNumber(vector<int>& nums) {
        int len = nums.size();
        int left = 0;
        int right = len - 1;

        while(left <= right){
            //int mid = ((right - left)>>1) + left; 
            int mid = ((left^right)>>1)+(left&right);  //不会溢出
            if(nums[mid] == mid){
                left = mid + 1;  //查找右半边
                if(left == len){  
                    return len;
                }
            }
            else{
                if(mid == 0 || nums[mid - 1] == mid-1){
                    return mid;
                }
                else{
                    right = mid - 1;
                }
            }
        }
        return {};
    }
}; 